package com.algorithm.dp;

/**
 * 查找目标总和方式
 *
 * @author Amadeus
 * @date 2023/10/23
 */
public class findTargetSumWays {

    public static int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int m = 0;
        if ((n + target) % 2 > 0) {
            return 0;
        }
        int left = (n + target) / 2;
        int[] dp = new int[left + 1];
        for (int i = 0; i < n; i++) {
            for (int j = left; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                System.out.println(dp[j]);
                if (dp[j] == left) {
                    m++;
                }
            }
        }
        return m;
    }

    public static void main(String[] args) {
        System.out.println(findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
    }
}
